//package leetcode;
//
//class Solution {
//    public boolean exists(char[][] board, String word) {
//        int width = board.length;
//        int high = board[0].length;
//        boolean[][] visited = new boolean[width][high];
//
//        for (int i = 0; i < width; i++) {
//            for (int j = 0; j < high; j++) {
//                boolean flag = check(board, visited, i, j, word, 0);
//                if (flag) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
//        if(board[i][j] != s.charAt(k)){
//            return false;
//        }else if(k == s.length() - 1){
//            return true;
//        }
//
//        visited[i][j] = true;
//        int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
//        boolean result = false;
//        for(int[] dir : directions){
//            int newi = i + dir[0];
//            int newj = j + dir[1];
//            if(newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length){
//                if(!visited[newi][newj]){
//                    boolean flag = check(board,visited,newi,newj,s,k+1);
//                    if(flag){
//                        result = true;
//                        break;
//                    }
//                }
//            }
//        }
//        visited[i][j] =false;
//        return result;
//    }
//}
//
//public class Test1 {
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        char[][] arr  = new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
//        String str = "ABCCED";
//        System.out.println(solution.exists(arr, str));
//    }
//}
